


public class merge{
private static int list [];


public merge(){
	list = new int [500];

}
//se devuleve la lsita ya ordenada 
public static int [] getlista(){
	return list;
}
   public static void mergeSort(int datos[], int largo)
  
    {
	//Despues de llamar al ciclomitad, se asigana la cadena ya ordenada a list
        ciclomitad(datos,new int[largo],0,largo-1);
		for(int e = 0; e<largo; e++){
			list[e]= datos[e];
		}
    }
     //se le ingresa los limites de la parte de la lista a analizar
    public static void ciclomitad(int[] first,
                                          int[] second,
                                          int primero, int ultimo)
  
    {	
		//se le da un largo a la lsita analizada
        int n = ultimo-primero+ 1; 
		// se le da una mitad a esa lista analizada
        int medio= primero+ n/2;
        
        
        if (n < 2) {
		//si el largo de la lsita es menor que dos, significa que no hay nada que hacer, porque ya esta ordenada, por ser de un solo digito
				}
			
		else{
        for (int i = primero; i < medio; i++) {
			//se le asigna, la parte baja de la lista analizada, a la segunda lista
            second[i] = first[i];
        }
		//se hace referencia al mismo metodo, para ordenar, la parte baja de la lista analizada,
        ciclomitad(second, first, primero, medio-1);
		//se hace referencia al mismo metodo, para odenar la parte alta de la lista
        ciclomitad(first, second, medio, ultimo);
       //se llama al metodo unioncadena, el cual compara cada poscion de cada una de las listas, y hace una sola cadena con todos losd atos ordenados
        unioncadena(first, second, primero, medio, ultimo);
		}
    }           
    //se ordena la cadena finalemnte
    public static void unioncadena(int[] first, int[] second,
                             int primero, int medio, int ultimo)
   
    {
        int destino = primero;           
        int inicio = primero;           
        int lim = medio;       
		//se compara cada posicion de las listas
        while (inicio < medio&& lim <= ultimo) {
			//si el dato que tiene la primera lista es mas peque;o que el primero de la segunda, es el primer dato que debe ir en la lista genera
            if (first[lim] < second[inicio]) {
                first[destino] = first[lim];  
				//es la pocicion de la lista total ordenada, al que se agregara el sigueinte dato
				destino++;
				//se avanza a la siguente posicion de la priemra lista, y la segunda se queda en lamisma pocicion, porque no se ha agregado a la lista total
				lim++;
            } else {
			//si el dato que tiene la segudnda lsita es menor que el de la primera, es este valor el que se agrega a la lista total
			//y se le suma uno al contador que lleva la pocicon de los datos en la segunda lista
                first[destino] = second[inicio];  
				destino++;
				inicio++;
            }
        }
		//luego de haber colocado todos los datos en la lista , pueden lelgar a hacer flata valor por agregar, q estaran en la segudna lsita
		
        
        while (inicio < medio) {
            first[destino] = second[inicio];
			destino++;
			inicio++;
        }
        
    }
    
    
	
	}
	
	
	
	
	
	